DSA: Graph- Spanning Tree

    Spanning Tree concept in Computer science is related to the Graph Data Structures, so do not confuse it with trees. A Spanning Tree is a subgraph or subset of a Graph G which contain all the vertices of the Graph G with the minimum number of edges. A graph can have more than one spanning tree and all the spanning trees of a graph must have all the vertices of that graph. As we know that tree data structure does not form a closed-loop or cycle so does spanning tree, all the spanning trees of a graph should not form a closed loop or cyclic structure.

    Spanning Tree

    When we design a spanning tree of a graph, that tree must contain all the vertices of the graph. We can also define a spanning tree as follow, “ a spanning tree is a connected graph G with all the vertices of G, that have a minimum number of edges and does not form a cyclic structure ”

    Example: 

     Graph
                         X
                       /   \
                      /     \
                     /       \
                    Y---------Z   

Spanning Trees

           X
            \
             \ 
              \
     Y---------Z


          X
        /   \
       /     \ 
      /       \
     Y         Z

 
          X
        /  
       /      
      /      
     Y---------Z

    We have a formula which can calculate the maximum number of spanning trees a complete graph could have. Suppose we have a complete undirected graph with node n so the maximum number of spanning trees of this graph would have n n-2 where n is the total number of nodes or vertices present in the graph. In the above example, we have a complete undirected graph with vertices X, Y and Z, which mean it has 3 vertices so the total number of spanning trees that could be formed from it are 3 3-2 = 3.

    Properties of a Spanning Tree

    As we can form more than one spanning tree from a graph, so while constructing a spanning tree we need to take care of some properties.

    • We can form a spanning tree from a connected graph.
    • The spanning-tree which is formed from a graph should have all the vertices of the Graph.
    • Like a tree, a spanning tree does not form a cyclic structure.
    • If we remove an edge from a spanning tree, it would make the graph disconnected which is also known as minimally connected
    • If we add an edge in the spanning tree it would make the graph cyclic.
    • A spanning tree can have n-1 number of edges where n is the number of nodes or vertices present in the graph.
    • We can only form n n-2 number of spanning trees from a complete disconnected graph.

    Real-world Applications of Spanning Tree

    There are many applications of Spanning tree and all of those are used to reduce the cost of a cluttered network.

    • Many pathfinding algorithms such as Dijkstra’s Algorithms and A* search algorithm, build spanning tree to solve the problem
    • To minimize the cost of a power network, for wiring connections, piping, automatic speech recognition we use spanning tree.
    • For internet and many other telecommunication networks transmission link we use spanning tree.
    • To find the shortest path while searching for a specific result on the internet.

    Minimum Spanning Tree

    In the graph, we have weighted graphs, in which a number or weight associated with every edge, the weight signifies the expense or cost of edge from one vertex to another. A minimum spanning tree is a spanning tree of a graph with minimum total weight. For example: 

     Weighted Graph               
                          X
                        /   \
                     10/     \20
                      /       \
                     Y---------Z
                         30

Spanning Trees

      X                                          
       \                                        
        \20                                      
         \                                         
  Y-------Z                                          
     30
             

         X
       /   \
    10/     \ 20
     /       \
    Y         Z
 minimum spanning tree


      X
    /  
 10/      
  /      
  Y---------Z
      30

    Algorithms of Minimum Spanning Tree

    There are two basic and most important spanning tree algorithms:

    • Kruskal’s Algorithm
    • Prim Algorithm

    People are also reading:

    Next Tutorial